/*
题目描述：实现Power函数，不需要考虑大数情况
方法：
需要考虑指数为负数和底数base为0的情况！
通过使用二分法可以加速幂乘过程
使用位运算要比乘除取余要快得多
通过与1进行与运算，可判断奇数偶数
 */
public class E16 {
    public static void main(String[] args){
        Solution A = new Solution();
        double base1 = 3.14;
        double base2 = 7;
        double base3 = -4;
        double base4 = 0;
        double base5 = 2;

        int exponent1 = 6;
        int exponent2 = 0;
        int exponent3 = 3;
        int exponent4 = -2;
        int exponent5 = -3;

        double res1 = A.Power(base1, exponent1);
        double res2 = A.Power(base2, exponent2);
        double res3 = A.Power(base3, exponent3);
        double res4 = A.Power(base4, exponent4);
        double res5 = A.Power(base5, exponent5);

        System.out.println("3.14^6 = " + res1);
        System.out.println("7^0 = " + res2);
        System.out.println("(-4)^3 = " + res3);
        System.out.println("0^(-2) = " + res4);
        System.out.println("2^(-3) = " + res5);
    }
}

class Solution{
    boolean invalidInput = false;
    public double Power(double base, int exponent) {
        invalidInput = false;
        if(Math.abs(base) == 0 && exponent < 0){
            invalidInput = true;
            return 0.0;
        }
        int absExponent = Math.abs(exponent);
        double result = powerWithUnsignedExponent2(base, absExponent);
        if(exponent < 0){
            result = 1/result;
        }
        return result;
    }
    //常规做法
    public double powerWithUnsignedExponent1(double base, int absExponent){
        double result = 1.0;
        for(int i = 0; i < absExponent; i++){
            result = result * base;
        }
        return result;
    }
    //极致效率
    public double powerWithUnsignedExponent2(double base, int absExponent){
        if(absExponent == 0){
            return 1;
        }
        if(absExponent == 1){
            return base;
        }

        double result = powerWithUnsignedExponent2(base, absExponent/2);
        result *= result;
        if((absExponent & 1) == 1){
            result *= base;
        }
        return result;
    }
}
